import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/26 9:00
 * @description 字典树变种
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"abab","baba","abba","baab"};
        System.out.println(solution.numWays(words, "abba"));
    }
    private int ans = 0;
    public int numWays(String[] words, String target) {
        back(words, target, 0, -1);
        return ans;
    }
    public void back(String[] words, String target, int curCh, int location) {
        if (curCh == target.length()) {
            ans++;
            return;
        }
        if (location + target.length() - curCh > target.length()) {
            return;
        }
        char ch = target.charAt(curCh);
        for(int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = location == -1 ? 0: location; j < word.length(); j++) {
                if (word.charAt(j) == ch) {
                    // 找到字符，可以开始遍历
                    back(words,  target, curCh + 1, j + 1);
                }
            }
        }
    }
}
